package liangtWorkSpace.sort;

/**
 * @ClassName AbjustSort
 * @Description : 功能说明
 * @Author : LiangT
 * @Date : 2020/4/17 10:59
 */

import java.util.Arrays;

/**
 * 堆排序，将数组组成最大或最小堆，依次进行输出，最后输出结果为堆排序
 */
public class AbjustSort {

    /**
     * 下沉操作
     * @param array
     * @param parentIndex
     * @param length
     */
    public static void downAdjust(int[] array,int parentIndex,int length){
        int temp = array[parentIndex];
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < length){
            if (childIndex +1  < length && array[childIndex + 1] >array[childIndex]) {
                childIndex ++;
            }
            if (temp > array[childIndex]){
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 堆升序排序
     * @param arry
     */
    public static void heapSort(int[] arry){
        for (int i = (arry.length - 2)/2; i >= 0; i--){
            downAdjust(arry,i,arry.length);
        }
        System.out.println(Arrays.toString(arry));
        for (int i = arry.length -1; i > 0; i--){
            int temp = arry[i];
            arry[i] = arry[0];
            arry[0] = temp;
            downAdjust(arry,0,i);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[] {1,3,2,6,5,7,8,9,10,0};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
